Computer programs typically make use of variables or similar labels to reference data “objects.” A portion of computer memory must be allocated during execution to each such object. Over time, as many such objects are created and used, the available, “free” memory that remains to be allocated in a particular system may begin to run short. As is well known in the art, a variety of methods and techniques have been proposed and implemented to reclaim as “free” and available those portions of computer memory that were originally allocated to program objects that are no longer in use by any running program. This task is generally known in the artas “garbage collection.” A great variety of different garbage collection techniques have been developed and used; for example, the reference paper Uniprocessor Garbage Collection Techniques by Paul R. Wilson (available through Internet via anonymous FTP from cs.utexas.edu as pub/garbage/bigsurv.ps) provides a broad survey of existing techniques, and explains commonly used terminology. That paper is incorporated herein in its entirety by this reference.
Prior art garbage collection systems have generally suffered to various degrees from the problem of excessive pause times. This problem arises when garbage collection is performed in real-time, i.e., concurrently with the execution of other live programs running on one or more processors. (In the field of garbage collection, the other live programs are typically referred to as “mutators,” because such programs potentially “mutate” or change the state of memory, from the point of view of the garbage collector or “GC.”)
For example, suppose that a system contains multiple mutator threads and a single GC thread. (A “thread” is an execution context within a shared address space, as discussed further below.) If the mutators are, for example, trying to present a movie at 30 frames per second, and they require a combined time of 23 ms to generate each frame, then problems will arise if the GC thread is run for more than loms during any particular 33 ms interval. It would therefore be desirable in this scenario to guarantee that the garbage collector will run no more than 30 times per second (i.e., its frequency will be no greater than 30; equivalently, its period will be greater than or equal to 33 ms), and also that each time the garbage collector is run it will execute for a maximum duration of no more than 10 ms.
GC frequency and duration can of course be kept “limited” through brute force, in the sense that the execution time allotted to the GC program may be explicitly rationed under control of the operating system or some other scheduling manager. This does not solve the problem at hand, however, because garbage collectors generally perform certain non-deferable, atomic work that must not be interrupted by mutators, at the risk of causing potential memory corruption. For example, a well-known family of GC schemes known as “copying” collectors (described in the Wilson survey paper, for example) actually copy, to a new location in memory, each data object that is determined not to be garbage (i.e., the object may still be in use by a live program). Since each such data object can potentially be arbitrarily large, and because the copying operation is necessarily atomic, a copying garbage collector may enter a phase where it cannot be interrupted by any mutator for an arbitrarily long period of time. Such GC schemes are generally not satisfactory for real-time systems where a maximum GC duration is required.
While non-copying garbage collectors also exist in the prior art (e.g., Henry G. Baker Jr., The Treadmill: Real-Time Garbage Collection Without Motion Sickness, SIGPLAN Notices Vol. 27 No. 3 at pp. 66-70, March 1992, incorporated herein in its entirety by this reference), many current applications of interest—notably, in the realm of multimedia—require limits on the maximum frequency and duration of garbage collection that the prior art has so far failed to dependably satisfy, at least on general-purpose stock hardware. As a result, systems running multimedia applications and the like have so far been unable to use garbage collection, and have instead been forced to rely on inconvenient, manual storage management techniques.